package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 134. 加油站
 * @date 2025/5/28 21:01
 */
public class E134 {

    /**
     * 思路就是所有加油站的油量和减去所有路程消耗的油量，
     * 如果结果小于0，则肯定无法完成一圈
     * 如果大于0，则肯定是能做到开完一圈的，只不过需要确定合适的起始加油站
     * 确定的过程就用currGasSubCost去做，如果当前小于0，则选i + 1作为新的起始加油站
     *
     * @param gas  汽油数组
     * @param cost 消耗数组
     * @return 加油站下标
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGasSubCost = 0, currGasSubCost = 0, startIndex = 0;
        for (int i = 0; i < gas.length; i++) {
            totalGasSubCost += gas[i] - cost[i];
            currGasSubCost += gas[i] - cost[i];
            if (currGasSubCost < 0) {
                currGasSubCost = 0;
                startIndex = i + 1;
            }
        }
        return totalGasSubCost < 0 ? -1 : startIndex;
    }
}
